// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package types2

import (
	"bytes"
	"cmd/compile/internal/syntax"
	"fmt"
	"sort"
)

// ---------------------------------------------------------------
// API 

// A u字体代表接口的类型集。
// 由于现有的语言限制，可以从术语中“排除”方法。实际类型集是方法所隐含的类型集
// 与术语所描述的类型集和
// 可比位的交集。要测试某个类型是否包含在类型集
// /（“implements”关系）中，该类型必须实现所有方法u和u是
// 由术语和可比较位描述的类型集的元素。
// 如果术语表描述了所有类型的集合，且可比为真，则
// 仅表示可比类型；在所有其他情况下，可比性都是错误的。
type _TypeSet struct {
	methods    []*Func  // 接口的所有方法；按唯一ID排序
	terms      termlist // 类型集的类型项
	comparable bool     // 不变量：！可比较的| |术语。isAll（）
}

// IsEmpty报告类型集s是否为空集。
func (s *_TypeSet) IsEmpty() bool { return s.terms.isEmpty() }

// IsAll报告类型集s是否是所有类型的集合（对应于空接口）。
func (s *_TypeSet) IsAll() bool { return s.IsMethodSet() && len(s.methods) == 0 }

// IsMethodSet报告接口t是否完全由其方法集描述。
func (s *_TypeSet) IsMethodSet() bool { return !s.comparable && s.terms.isAll() }

// IsCompatible报告集合中的每种类型是否具有可比性。
func (s *_TypeSet) IsComparable(seen map[Type]bool) bool {
	if s.terms.isAll() {
		return s.comparable
	}
	return s.is(func(t *term) bool {
		return t != nil && comparable(t.typ, false, seen, nil)
	})
}

// NumMethods返回可用的方法数。
func (s *_TypeSet) NumMethods() int { return len(s.methods) }

// 方法返回0<=i<s.NumMethods（）的类型集s的第i个方法。
// 这些方法按其唯一ID排序。
func (s *_TypeSet) Method(i int) *Func { return s.methods[i] }

// LookupMethod返回and方法的索引，其中包含匹配的包和名称，或（-1，nil）。
func (s *_TypeSet) LookupMethod(pkg *Package, name string, foldCase bool) (int, *Func) {
	return lookupMethod(s.methods, pkg, name, foldCase)
}

func (s *_TypeSet) String() string {
	switch {
	case s.IsEmpty():
		return "∅"
	case s.IsAll():
		return "𝓤"
	}

	hasMethods := len(s.methods) > 0
	hasTerms := s.hasTerms()

	var buf bytes.Buffer
	buf.WriteByte('{')
	if s.comparable {
		buf.WriteString("comparable")
		if hasMethods || hasTerms {
			buf.WriteString("; ")
		}
	}
	for i, m := range s.methods {
		if i > 0 {
			buf.WriteString("; ")
		}
		buf.WriteString(m.String())
	}
	if hasMethods && hasTerms {
		buf.WriteString("; ")
	}
	if hasTerms {
		buf.WriteString(s.terms.String())
	}
	buf.WriteString("}")
	return buf.String()
}

// ---------------------------------------------------------------
// 实现

// hasTerms报告类型集是否具有特定的类型术语。
func (s *_TypeSet) hasTerms() bool { return !s.terms.isEmpty() && !s.terms.isAll() }

// 子部分报告s1⊆ s2。
func (s1 *_TypeSet) subsetOf(s2 *_TypeSet) bool { return s1.terms.subsetOf(s2.terms) }

// TODO（gri）字体。这是我的工作和排版。underIs可能也应该进入termlist。go 

// is调用具有特定类型项s的f，并报告
// 是否所有对f的调用都返回true。如果没有具体的术语，is 
// 返回f（nil）的结果。
func (s *_TypeSet) is(f func(*term) bool) bool {
	if !s.hasTerms() {
		return f(nil)
	}
	for _, t := range s.terms {
		assert(t.typ != nil)
		if !f(t) {
			return false
		}
	}
	return true
}

// underIs使用特定类型项的基础类型
// s调用f，并报告是否所有对f的调用都返回true。如果有
// 没有具体条款，underIs返回f（nil）的结果。
func (s *_TypeSet) underIs(f func(Type) bool) bool {
	if !s.hasTerms() {
		return f(nil)
	}
	for _, t := range s.terms {
		assert(t.typ != nil)
		// x==在（x）下表示~x个术语
		u := t.typ
		if !t.tilde {
			u = under(u)
		}
		if debug {
			assert(Identical(u, under(u)))
		}
		if !f(u) {
			return false
		}
	}
	return true
}

// topTypeSet可以用作空接口的类型集。
var topTypeSet = _TypeSet{terms: allTermlist}

// computeInterfaceTypeSet可以用check==nil调用。
func computeInterfaceTypeSet(check *Checker, pos syntax.Pos, ityp *Interface) *_TypeSet {
	if ityp.tset != nil {
		return ityp.tset
	}

	// 如果接口尚未完全设置，则类型集将
	// 不完整，这可能导致使用
	// 类型集时出错（例如缺少方法）。不要计算部分类型
	// set（不要存储它！），所以我们最终还是要计算完整的
	// 类型集。相反，返回top类型集，并让任何后续错误显示出来。
	if !ityp.complete {
		return &topTypeSet
	}

	if check != nil && check.conf.Trace {
		// 类型通常没有位置信息。
		// 如果我们没有提供有效的pos，请尝试使用
		// 一个足够接近的pos。
		if !pos.IsKnown() && len(ityp.methods) > 0 {
			pos = ityp.methods[0].pos
		}

		check.trace(pos, "type set for %s", ityp)
		check.indent++
		defer func() {
			check.indent--
			check.trace(pos, "=> %s ", ityp.typeSet())
		}()
	}

	// 在其他地方（Checker.validType）检测到无限扩展的接口（由于一个循环），所以这里我们只假设只有
	// 有有效的接口。如果由于某些原因，validType检查在以后发生，请将接口标记为complete，以避免无限递归。这就足够了吗？

	var unionSets map[*Union]*_TypeSet
	if check != nil {
		if check.unionTypeSets == nil {
			check.unionTypeSets = make(map[*Union]*_TypeSet)
		}
		unionSets = check.unionTypeSets
	} else {
		unionSets = make(map[*Union]*_TypeSet)
	}

	// 嵌入式接口的采集方法不变；i、 例如，接口i的方法i.m的Func对象的标识
	// 与嵌入接口i的接口中的方法m的标识
	// 相同。另一方面，如果一个方法通过多个重叠的嵌入接口嵌入，我们不保证嵌入
	// 接口选择了哪个“原始m”。另见第34421期。
	// 
	// 如果我们不想再提供这种身份保证，我们可以克隆该方法的Func 
	// 在嵌入中重用原始方法。然后
	// 对象，并给它一个相应的嵌入接口的位置，而不是
	// 我们可以去掉下面的mpos映射，只需使用克隆方法的
	// 位置。

	var todo []*Func
	var seen objset
	var allMethods []*Func
	mpos := make(map[*Func]syntax.Pos) // 方法规范或方法嵌入位置，对于良好的错误消息
	addMethod := func(pos syntax.Pos, m *Func, explicit bool) {
		switch other := seen.insert(m); {
		case other == nil:
			allMethods = append(allMethods, m)
			mpos[m] = pos
		case explicit:
			if check == nil {
				panic(fmt.Sprintf("%s: duplicate method %s", m.pos, m.name))
			}
			// 检查！=nil 
			var err error_
			err.errorf(pos, "duplicate method %s", m.name)
			err.errorf(mpos[other.(*Func)], "other declaration of %s", m.name)
			check.report(&err)
		default:
			// 我们在一个嵌入（未显式声明）方法中有一个重复的方法名。
			// 计算所有类型后检查方法签名（问题#33656）。
			// 如果我们在go1之前。14（不允许重叠嵌入），在这里报告
			// 错误（尽管我们可以急切地这样做），因为它是相同的
			// 错误消息。
			if check == nil {
				// 计算所有本地嵌入接口后检查方法签名
				todo = append(todo, m, other.(*Func))
				break
			}
			// 检查！=nil 
			check.later(func() {
				if !check.allowVersion(m.pkg, 1, 14) || !Identical(m.typ, other.Type()) {
					var err error_
					err.errorf(pos, "duplicate method %s", m.name)
					err.errorf(mpos[other.(*Func)], "other declaration of %s", m.name)
					check.report(&err)
				}
			})
		}
	}

	for _, m := range ityp.methods {
		addMethod(m.pos, m, true)
	}

	// 收集嵌入元素
	allTerms := allTermlist
	allComparable := false
	for i, typ := range ityp.embeddeds {
		// 对于导入的接口
		// 以及替换后的接口副本，嵌入位置为零（但是
		// 在这种情况下，我们不需要再次报告错误）。
		var pos syntax.Pos // 嵌入位置
		if ityp.embedPos != nil {
			pos = (*ityp.embedPos)[i]
		}
		var comparable bool
		var terms termlist
		switch u := under(typ).(type) {
		case *Interface:
			// 目前我们不允许类型参数作为约束。
			assert(!isTypeParam(typ))
			tset := computeInterfaceTypeSet(check, pos, u)
			// 如果类型是本地的，则在指定/定义类型的位置已报告错误。
			if check != nil && check.isImportedConstraint(typ) && !check.allowVersion(check.pkg, 1, 18) {
				check.versionErrorf(pos, "go1.18", "embedding constraint interface %s", typ)
				continue
			}
			comparable = tset.comparable
			for _, m := range tset.methods {
				addMethod(pos, m, false) // 使用嵌入位置pos而不是m.pos 
			}
			terms = tset.terms
		case *Union:
			if check != nil && !check.allowVersion(check.pkg, 1, 18) {
				check.versionErrorf(pos, "go1.18", "embedding interface element %s", u)
				continue
			}
			tset := computeUnionTypeSet(check, unionSets, pos, u)
			if tset == &invalidTypeSet {
				continue // 忽略无效的联合
			}
			assert(!tset.comparable)
			assert(len(tset.methods) == 0)
			terms = tset.terms
		default:
			if u == Typ[Invalid] {
				continue
			}
			if check != nil && !check.allowVersion(check.pkg, 1, 18) {
				check.versionErrorf(pos, "go1.18", "embedding non-interface type %s", typ)
				continue
			}
			terms = termlist{{false, typ}}
		}

		// 接口的类型集是其所有元素的类型集的交集。
		// 由于语言限制，只有嵌入式接口可以添加方法，它们分别处理
		// 。在这里，我们只需要将术语列表和可比较的位相交。
		allTerms, allComparable = intersectTermLists(allTerms, allComparable, terms, comparable)
	}
	ityp.embedPos = nil // 不再需要（已报告错误）

	// 处理todo（仅当check==nil时发生）
	for i := 0; i < len(todo); i += 2 {
		m := todo[i]
		other := todo[i+1]
		if !Identical(m.typ, other.typ) {
			panic(fmt.Sprintf("%s: duplicate method %s", m.pos, m.name))
		}
	}

	ityp.tset.comparable = allComparable
	if len(allMethods) != 0 {
		sortMethods(allMethods)
		ityp.tset.methods = allMethods
	}
	ityp.tset.terms = allTerms

	return ityp.tset
}

// todo（gri）IntersectTermList函数属于termlist实现。
// 可比类型集也可以最好地表示为一个术语（使用
// 一个特殊类型）。

// intersectTermLists计算两个术语列表和各自可比较位的交集。
// xcomp，ycomp仅在xterms时有效。isAll（）和yterms。分别是isAll（）。
func intersectTermLists(xterms termlist, xcomp bool, yterms termlist, ycomp bool) (termlist, bool) {
	terms := xterms.intersect(yterms)
	// 如果XTERM或YTERM中的一个标记为可比较，
	// 结果必须只包含可比较的类型。
	comp := xcomp || ycomp
	if comp && !terms.isAll() {
		// 仅保留可比较项
		i := 0
		for _, t := range terms {
			assert(t.typ != nil)
			if Comparable(t.typ) {
				terms[i] = t
				i++
			}
		}
		terms = terms[:i]
		if !terms.isAll() {
			comp = false
		}
	}
	assert(!comp || terms.isAll()) // 可比较不变
	return terms, comp
}

func sortMethods(list []*Func) {
	sort.Sort(byUniqueMethodName(list))
}

func assertSortedMethods(list []*Func) {
	if !debug {
		panic("assertSortedMethods called outside debug mode")
	}
	if !sort.IsSorted(byUniqueMethodName(list)) {
		panic("methods not sorted")
	}
}

// byUniqueMethodName方法列表可以按其唯一的方法名称排序。
type byUniqueMethodName []*Func

func (a byUniqueMethodName) Len() int           { return len(a) }
func (a byUniqueMethodName) Less(i, j int) bool { return a[i].less(&a[j].object) }
func (a byUniqueMethodName) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// invalidTypeSet是一个单例类型集，用于表示由于错误导致的无效类型集
// 。它也是一个有效的空类型集，因此
// 类型集的使用者可以选择忽略它。
var invalidTypeSet _TypeSet

// 可以使用check==nil调用ComputeUnityPeset。
// 如果联合溢出，则结果为&invalidTypeSet。
func computeUnionTypeSet(check *Checker, unionSets map[*Union]*_TypeSet, pos syntax.Pos, utyp *Union) *_TypeSet {
	if tset, _ := unionSets[utyp]; tset != nil {
		return tset
	}

	// 避免无限递归（另请参见computeInterfaceTypeSet）
	unionSets[utyp] = new(_TypeSet)

	var allTerms termlist
	for _, t := range utyp.terms {
		var terms termlist
		u := under(t.typ)
		if ui, _ := u.(*Interface); ui != nil {
			// 目前我们不允许类型参数作为约束。
			assert(!isTypeParam(t.typ))
			terms = computeInterfaceTypeSet(check, pos, ui).terms
		} else if u == Typ[Invalid] {
			continue
		} else {
			if t.tilde && !Identical(t.typ, u) {
				// 没有t.typ的基础类型。
				// 对应的类型集为空。
				t = nil // ∅ term 
			}
			terms = termlist{(*term)(t)}
		}
		// union表达式的类型集是每个term的类型集的union 
		// 。
		allTerms = allTerms.union(terms)
		if len(allTerms) > maxTermCount {
			if check != nil {
				check.errorf(pos, "cannot handle more than %d union terms (implementation limitation)", maxTermCount)
			}
			unionSets[utyp] = &invalidTypeSet
			return unionSets[utyp]
		}
	}
	unionSets[utyp].terms = allTerms

	return unionSets[utyp]
}
